/** ANSI C ANTLR v3 grammar

Translated from Jutta Degener's 1995 ANSI C yacc grammar by Terence Parr
July 2006.  The lexical rules were taken from the Java grammar.

Jutta says: "In 1985, Jeff Lee published his Yacc grammar (which
is accompanied by a matching Lex specification) for the April 30, 1985 draft
version of the ANSI C standard.  Tom Stockfisch reposted it to net.sources in
1987; that original, as mentioned in the answer to question 17.25 of the
comp.lang.c FAQ, can be ftp'ed from ftp.uu.net,
   file usenet/net.sources/ansi.c.grammar.Z.
I intend to keep this version as close to the current C Standard grammar as
possible; please let me know if you discover discrepancies. Jutta Degener, 1995"

Generally speaking, you need symbol table info to parse C; typedefs
define types and then IDENTIFIERS are either types or plain IDs.  I'm doing
the min necessary here tracking only type names.  This is a good example
of the global scope (called Symbols).  Every rule that declares its usage
of Symbols pushes a new copy on the stack effectively creating a new
symbol scope.  Also note rule declaration declares a rule scope that
lets any invoked rule see isTypedef boolean.  It's much easier than
passing that info down as parameters.  Very clean.  Rule
direct_declarator can then easily determine whether the IDENTIFIER
should be declared as a type name.

I have only tested this on a single file, though it is 3500 lines.

This grammar requires ANTLR v3.0.1 or higher.

Terence Parr
July 2006
*/
grammar C;
options {
    backtrack=true;
    memoize=true;
    k=2;
    language=Python;
    output=AST;
    ASTLabelType=CommonTree;
}

tokens {
	TRANSLATION_UNIT;
	DECLARATION;
	FUNCTION_DEFIN;
	FUNCTION_DECL;
	FUNCTION_BODY;
	TYPEDEF;
	DECL_SPEC;
	INIT_DECL;
	STRUCT_SPECIFIER;
	UNION_SPECIFIER;
	STRUCT_DECL;
	STRUCT_DECL_WITH_DECLARATOR;
	STRUCT_DECL_NO_DECLARATOR;
	ENUM_DECL;
	ENUMERATOR_LIST;
	DECLARATOR_WITH_POINTER;
	DECLARATOR;
	DECLARATOR_SUFFIX;
	DECLARATOR_SUFFIX_ARR;
	DECLARATOR_SUFFIX_FUNC;
	POINTER;
	PARAMETER_LIST;
	PARAMETER_DECLARATION;
	ID_LIST;
	TYPE_NAME;
	ABSTRACT_DECL;
	ABSTRACT_DECL_SUFFIX_ARR;
	ABSTRACT_DECL_SUFFIX_FUNC;
	INITIALIZER;
	
	ARGUMENT_EXPRESSION_LIST;
//	ADDITIVE_EXPRESSION;
//	MULTIPLICATIVE_EXPRESSION;
	CAST_EXPRESSION;
	UNARY_EXPRESSION_DEC;
	UNARY_EXPRESSION_INC;
	UNARY_EXPRESSION_SIZEOF;
	UNARY_EXPRESSION_CAST;
	UNARY_EXPRESSION_POSTFIX;
	UNARY_EXPRESSION_OPER;

	POSTFIX_EXPRESSION_ARG;
	POSTFIX_EXPRESSION_EXPR;
	POSTFIX_EXPRESSION_DOT;
	POSTFIX_EXPRESSION_DEREF;
	POSTFIX_EXPRESSION_DEC;
	POSTFIX_EXPRESSION_INC;
	
	PRIMARY_EXPRESSION;
	
	CONSTANT_HEX;
	CONSTANT_OCT;
	CONSTANT_DEC;
	CONSTANT_CHAR;
	CONSTANT_STR;
	CONSTANT_FLOAT;

	EXPRESSION;
	ASSIGNMENT_EXPR;
	CONDITIONAL_EXPR;
	LVALUE;	
	LOGICAL_OR_EXPR;
	LOGICAL_AND_EXPR;
	INCLUSIVE_OR_EXPR;
	EXCLUSIVE_OR_EXPR;
	AND_EXPR;
	EQUALITY_EXPR;
	RELATIONAL_EXPR;
	SHIFT_EXPR;
}

scope Symbols {
	types;
}

@header { import string }

@members {
	def isTypeName( self, name ):
		for i in $Symbols:
			if ( name in i.types ):
				return True
		return False
}

translation_unit
scope Symbols; // entire file is a scope
@init {
  $Symbols::types = [ ];
}
	: external_declaration+ -> ^(TRANSLATION_UNIT external_declaration+)
	;
	
/** Either a function definition or any other kind of C decl/def.
 *  The LL(*) analysis algorithm fails to deal with this due to
 *  recursion in the declarator rules.  I'm putting in a
 *  manual predicate here so that we don't backtrack over
 *  the entire function.  Further, you get a better error
 *  as errors within the function itself don't make it fail
 *  to predict that it's a function.  Weird errors previously.
 *  Remember: the goal is to avoid backtrack like the plague
 *  because it makes debugging, actions, and errors harder.
 *
 *  Note that k=1 results in a much smaller predictor for the 
 *  fixed lookahead; k=2 made a few extra thousand lines. ;)
 *  I'll have to optimize that in the future.
 */
external_declaration
options {k=1;}
	: (( declaration_specifier_list? declarator declaration* '{' )=> function_definition) -> ^(FUNCTION_DEFIN function_definition)
	| declaration
	; 

function_definition
scope Symbols; // put parameters and locals into same scope for now
@init {
  $Symbols::types = [ ];
}
	:	declaration_specifier_list? declarator
		(	declaration+ compound_statement	// K&R style
		|	compound_statement				// ANSI style
		) -> ^(FUNCTION_DECL declaration_specifier_list? declarator)  declaration* ^(FUNCTION_BODY compound_statement)
	;

declaration
scope {
  isTypedef;
}
@init {
  $declaration::isTypedef = False;
}
 	: 'typedef' declaration_specifier_list? {$declaration::isTypedef=True;} // special case, looking for typedef	
	  init_declarator_list ';' -> ^(TYPEDEF declaration_specifier_list? init_declarator_list)
	| declaration_specifier_list init_declarator_list? ';' -> ^(DECLARATION declaration_specifier_list init_declarator_list?)
	;

declaration_specifier_list
	: declaration_specifier+ 
	;
declaration_specifier
	: ( storage_class_specifier	
	|   type_specifier		
        |   type_qualifier ) -> ^(DECL_SPEC storage_class_specifier? type_specifier? type_qualifier? )
        ;

init_declarator_list
	: init_declarator (',' init_declarator)*
	;

init_declarator
	: declarator ('=' initializer)? -> ^(INIT_DECL declarator initializer?)
	;

storage_class_specifier
	: 'extern'
	| 'static'
	| 'auto'
	| 'register'
	;

type_specifier
	: 'void'
	| 'char'
	| 'short'
	| 'int'
	| 'long'
	| 'float'
	| 'double'
	| 'signed'
	| 'unsigned'
	| struct_or_union_specifier
	| enum_specifier
	| type_id
	;

type_id
    :   {self.isTypeName( self.input.LT(1).getText() )}? IDENTIFIER
//    	{System.out.println($IDENTIFIER.text+" is a type");}
    ;

struct_or_union_specifier
options {k=3;}
scope Symbols; // structs are scopes
@init {
  $Symbols::types = [ ];
}
	: 'struct' IDENTIFIER? '{' struct_declaration_list '}' -> ^(STRUCT_SPECIFIER IDENTIFIER? struct_declaration_list )
	| 'struct' IDENTIFIER -> ^(STRUCT_SPECIFIER IDENTIFIER)
	| 'union' IDENTIFIER? '{' struct_declaration_list '}' -> ^(UNION_SPECIFIER IDENTIFIER? struct_declaration_list )
	| 'union' IDENTIFIER -> ^(UNION_SPECIFIER IDENTIFIER)
	;

struct_declaration_list
	: struct_declaration+
	;

struct_declaration
	: specifier_qualifier_list struct_declarator_list ';' -> ^(STRUCT_DECL specifier_qualifier_list struct_declarator_list)
	;

specifier_qualifier_list
	: specifier_qualifier+
	;
	
specifier_qualifier
	: ( type_qualifier | type_specifier ) -> ^(DECL_SPEC type_qualifier? type_specifier? )
	;

struct_declarator_list
	: struct_declarator (',' struct_declarator)*
	;

struct_declarator
	: declarator (':' constant_expression)? -> ^(STRUCT_DECL_WITH_DECLARATOR declarator constant_expression?)
	| ':' constant_expression -> ^(STRUCT_DECL_NO_DECLARATOR constant_expression)
	;

enum_specifier
options {k=3;}
	: 'enum' '{' enumerator_list '}' -> ^(ENUM_DECL enumerator_list)
	| 'enum' IDENTIFIER '{' enumerator_list '}' -> ^(ENUM_DECL IDENTIFIER enumerator_list)
	| 'enum' IDENTIFIER -> ^(ENUM_DECL IDENTIFIER)
	;

enumerator_list
	: enumerator (',' enumerator)* -> ^(ENUMERATOR_LIST enumerator*)
	;

enumerator
	: IDENTIFIER ('=' constant_expression)? -> ^(IDENTIFIER constant_expression?)
	;

type_qualifier
	: 'const'
	| 'volatile'
	;

declarator
	: (pointer? direct_declarator
	| pointer) -> ^(DECLARATOR_WITH_POINTER pointer? direct_declarator?)
	;

direct_declarator
	:   (	IDENTIFIER
			{
			if ( ( len($declaration)>0) and ($declaration::isTypedef) ):
				$Symbols::types.append($IDENTIFIER.text)
			}
		|	'(' declarator ')'
		)
        declarator_suffix* -> ^(DECLARATOR_SUFFIX IDENTIFIER? declarator? declarator_suffix*)
	;

declarator_suffix
	:   '[' constant_expression ']' -> ^(DECLARATOR_SUFFIX_ARR constant_expression)
   	|   '[' ']' -> ^(DECLARATOR_SUFFIX_ARR)
  	|   '(' parameter_type_list ')' -> ^(DECLARATOR_SUFFIX_FUNC parameter_type_list)
  	|   '(' identifier_list ')' -> ^(DECLARATOR_SUFFIX_FUNC identifier_list)
  	|   '(' ')' -> ^(DECLARATOR_SUFFIX_FUNC)
	;

pointer
	: '*' type_qualifier+ pointer? -> ^(POINTER type_qualifier+ pointer?)
	| '*' pointer -> ^(POINTER pointer)
	| '*' -> ^(POINTER)
	;

parameter_type_list
	: parameter_list (',' '...')?
	;

parameter_list
	: parameter_declaration (',' parameter_declaration)* -> ^(PARAMETER_LIST parameter_declaration+)
	;

parameter_declaration
	: declaration_specifier_list (declarator|abstract_declarator)* -> ^(PARAMETER_DECLARATION declaration_specifier_list declarator* abstract_declarator*)
	;

identifier_list
	: IDENTIFIER (',' IDENTIFIER)* -> ^(ID_LIST IDENTIFIER+)
	;

type_name
	: specifier_qualifier_list abstract_declarator? -> ^(TYPE_NAME specifier_qualifier_list abstract_declarator?)
	;

abstract_declarator
	: (pointer direct_abstract_declarator?
	| direct_abstract_declarator) -> ^(ABSTRACT_DECL pointer? direct_abstract_declarator)
	;

direct_abstract_declarator
	: ( '(' abstract_declarator ')' | abstract_declarator_suffix ) abstract_declarator_suffix*
	;

abstract_declarator_suffix
	:	'[' ']' -> ^(ABSTRACT_DECL_SUFFIX_ARR)
	|	'[' constant_expression ']' -> ^(ABSTRACT_DECL_SUFFIX_ARR constant_expression)
	|	'(' ')' -> ^(ABSTRACT_DECL_SUFFIX_FUNC)
	|	'(' parameter_type_list ')' -> ^(ABSTRACT_DECL_SUFFIX_FUNC parameter_type_list)
	;
	
initializer
	: (assignment_expression
	| '{' initializer_list ','? '}') -> ^(INITIALIZER assignment_expression? initializer_list?)
	;

initializer_list
	: initializer (',' initializer)*
	;

// E x p r e s s i o n s

argument_expression_list
	:   assignment_expression (',' assignment_expression)* -> ^(ARGUMENT_EXPRESSION_LIST assignment_expression+)
	;

additive_expression
	: multiplicative_expression ('+'^ multiplicative_expression | '-'^ multiplicative_expression)*
	;

multiplicative_expression
	: (cast_expression) ('*'^ cast_expression | '/'^ cast_expression | '%'^ cast_expression)*
	;

cast_expression
	: '(' type_name ')' cast_expression -> ^(CAST_EXPRESSION type_name cast_expression)
	| unary_expression -> ^(CAST_EXPRESSION unary_expression)
	;

unary_expression
	: postfix_expression -> ^(UNARY_EXPRESSION_POSTFIX postfix_expression)
	| '++' unary_expression -> ^(UNARY_EXPRESSION_INC unary_expression)
	| '--' unary_expression -> ^(UNARY_EXPRESSION_DEC unary_expression)
	| unary_operator cast_expression -> ^(UNARY_EXPRESSION_OPER unary_operator cast_expression)
	| 'sizeof' unary_expression -> ^(UNARY_EXPRESSION_SIZEOF unary_expression)
	| 'sizeof' '(' type_name ')'-> ^(UNARY_EXPRESSION_SIZEOF type_name)
	;

postfix_expression_expr
	: '[' expression ']' -> ^(POSTFIX_EXPRESSION_EXPR expression);
	
postfix_expression_arg
	: '(' ')' -> ^(POSTFIX_EXPRESSION_ARG)
	| '(' argument_expression_list ')' -> ^(POSTFIX_EXPRESSION_ARG argument_expression_list);
	
postfix_expression_dot
	:  '.' IDENTIFIER -> ^(POSTFIX_EXPRESSION_DOT IDENTIFIER);

postfix_expression_deref
	: '->' IDENTIFIER -> ^(POSTFIX_EXPRESSION_DEREF IDENTIFIER);

postfix_expression_inc
	: '++' -> ^(POSTFIX_EXPRESSION_INC);
	
postfix_expression_dec
	: '--' -> ^(POSTFIX_EXPRESSION_DEC);
	
postfix_expression
	:   primary_expression
        ( postfix_expression_expr
        | postfix_expression_arg
        | postfix_expression_dot
        | postfix_expression_deref
        | postfix_expression_inc
	| postfix_expression_dec
        )*
	;    

unary_operator
	: '&'
	| '*'
	| '+'
	| '-'
	| '~'
	| '!'
	;

primary_expression
	: IDENTIFIER -> ^(PRIMARY_EXPRESSION IDENTIFIER)
	| constant -> ^(PRIMARY_EXPRESSION constant)
	| '(' expression ')' -> ^(PRIMARY_EXPRESSION expression)
	;

constant
    :   HEX_LITERAL -> ^(CONSTANT_HEX HEX_LITERAL)
    |   OCTAL_LITERAL -> ^(CONSTANT_OCT OCTAL_LITERAL)
    |   DECIMAL_LITERAL -> ^(CONSTANT_DEC DECIMAL_LITERAL)
    |	CHARACTER_LITERAL -> ^(CONSTANT_CHAR CHARACTER_LITERAL)
    |	STRING_LITERAL -> ^(CONSTANT_STR STRING_LITERAL)
    |   FLOATING_POINT_LITERAL -> ^(CONSTANT_FLOAT FLOATING_POINT_LITERAL)
    ;

/////

expression
	: assignment_expression (',' assignment_expression)* -> ^(EXPRESSION assignment_expression+)
	;

constant_expression
	: conditional_expression
	;

assignment_expression
	: lvalue assignment_operator assignment_expression -> ^(ASSIGNMENT_EXPR lvalue assignment_operator assignment_expression)
	| conditional_expression
	;
	
lvalue
	: unary_expression -> ^(LVALUE unary_expression)
	;

assignment_operator
	:  ( '='
	| '*='
	| '/='
	| '%='
	| '+='
	| '-='
	| '<<='
	| '>>='
	| '&='
	| '^='
	| '|=' )
	;

conditional_expression
	: logical_or_expression ('?' expression ':' conditional_expression)? -> ^(CONDITIONAL_EXPR logical_or_expression expression? conditional_expression?)
	;

logical_or_expression
	: logical_and_expression ('||' logical_and_expression)* -> ^(LOGICAL_OR_EXPR logical_and_expression+)
	;

logical_and_expression
	: inclusive_or_expression ('&&' inclusive_or_expression)* -> ^(LOGICAL_AND_EXPR inclusive_or_expression+)
	;


exclusive_or_expression
	: and_expression ('^' and_expression)* -> ^(EXCLUSIVE_OR_EXPR and_expression+)
	;
	
inclusive_or_expression
	: exclusive_or_expression ('|' exclusive_or_expression)* -> ^(INCLUSIVE_OR_EXPR exclusive_or_expression+)
	;


and_expression
	: equality_expression ('&' equality_expression)* -> ^(AND_EXPR equality_expression+)
	;
	
equality_expression
	: relational_expression (equality_oper relational_expression)* -> ^(EQUALITY_EXPR relational_expression equality_oper* relational_expression*)
	;
	
equality_oper
	: ('=='|'!=')
	;

relational_expression
	: shift_expression (relational_oper shift_expression)* -> ^(RELATIONAL_EXPR shift_expression relational_oper* shift_expression*)
	;

relational_oper
	: ('<'|'>'|'<='|'>=')
	;

shift_expression
	: additive_expression (shift_oper additive_expression)* -> ^(SHIFT_EXPR additive_expression shift_oper* additive_expression*)
	;
	
shift_oper
	: ('<<'|'>>')
	;

// S t a t e m e n t s

statement
	: labeled_statement
	| compound_statement
	| expression_statement
	| selection_statement
	| iteration_statement
	| jump_statement
	;

labeled_statement
	: IDENTIFIER ':' statement
	| 'case' constant_expression ':' statement
	| 'default' ':' statement
	;

compound_statement
scope Symbols; // blocks have a scope of symbols
@init {
  $Symbols::types = [ ];
}
	: '{' declaration* statement_list? '}'
	;

statement_list
	: statement+
	;

expression_statement
	: ';'
	| expression ';'
	;

selection_statement
	: 'if' '(' expression ')' statement (options {k=1; backtrack=false;}:'else' statement)?
	| 'switch' '(' expression ')' statement
	;
	
iteration_statement
	: 'while' '(' expression ')' statement
	| 'do' statement 'while' '(' expression ')' ';'				
	| 'for' '(' expression_statement expression_statement expression? ')' statement
	;

jump_statement
	: 'goto' IDENTIFIER ';'
	| 'continue' ';' 
	| 'break' ';' 
	| 'return' ';'				
	| 'return' expression ';'
	;

IDENTIFIER
	:	LETTER (LETTER|'0'..'9')*
	;
	
fragment
LETTER
	:	'$'
	|	'A'..'Z'
	|	'a'..'z'
	|	'_'
	;

CHARACTER_LITERAL
    :   '\'' ( EscapeSequence | ~('\''|'\\') ) '\''
    ;

STRING_LITERAL
    :  '"' ( EscapeSequence | ~('\\'|'"') )* '"'
    ;

HEX_LITERAL : '0' ('x'|'X') HexDigit+ IntegerTypeSuffix? ;

DECIMAL_LITERAL : ('0' | '1'..'9' '0'..'9'*) IntegerTypeSuffix? ;

OCTAL_LITERAL : '0' ('0'..'7')+ IntegerTypeSuffix? ;

fragment
HexDigit : ('0'..'9'|'a'..'f'|'A'..'F') ;

fragment
IntegerTypeSuffix
	:	('u'|'U')? ('l'|'L')
	|	('u'|'U')  ('l'|'L')?
	;

FLOATING_POINT_LITERAL
    :   ('0'..'9')+ '.' ('0'..'9')* Exponent? FloatTypeSuffix?
    |   '.' ('0'..'9')+ Exponent? FloatTypeSuffix?
    |   ('0'..'9')+ Exponent FloatTypeSuffix?
    |   ('0'..'9')+ Exponent? FloatTypeSuffix
	;

fragment
Exponent : ('e'|'E') ('+'|'-')? ('0'..'9')+ ;

fragment
FloatTypeSuffix : ('f'|'F'|'d'|'D') ;

fragment
EscapeSequence
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   OctalEscape
    ;

fragment
OctalEscape
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UnicodeEscape
    :   '\\' 'u' HexDigit HexDigit HexDigit HexDigit
    ;

WS  :  (' '|'\r'|'\t'|'\u000C'|'\n') {$channel=HIDDEN;}
    ;

COMMENT
    :   '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
    ;

LINE_COMMENT
    : '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    ;

// ignore #line info for now
LINE_COMMAND 
    : '#' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    ;
